/**
 * 146. LRU 缓存
 * https://leetcode-cn.com/problems/lru-cache/
 */

/**
 * @param {number} key
 * @param {number} val
 * @constructor
 */
function TwoWayNode(key, val) {
  this.key = key;
  this.val = val;
  this.pre = null;
  this.next = null;
}

/**
 * @param {number} capacity
 */
function LRUCache(capacity) {
  this.capacity = capacity;
  this.length = 0;
  const head = new TwoWayNode(0, 0);
  const tail = new TwoWayNode(0, 0);
  head.next = tail;
  tail.pre = head;
  this.head = head;
  this.tail = tail;
  this.map = new Array(10001);
}

/**
 * @param {TwoWayNode} node
 * @param {TwoWayNode} head
 */
function update(node, head) {
  const { pre, next } = node;
  pre.next = next;
  next.pre = pre;
  const first = head.next;
  node.next = first;
  first.pre = node;
  head.next = node;
  node.pre = head;
}

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  const { map, head } = this;
  const node = map[key];
  if (node) {
    update(node, head);
    return node.val;
  }
  return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  const {
    map, head, tail, capacity,
  } = this;
  let node = map[key];
  if (node) {
    update(node, head);
    node.val = value;
    return;
  }
  if (this.length >= capacity) {
    const last = tail.pre;
    const { pre } = last;
    pre.next = tail;
    tail.pre = pre;
    last.pre = null;
    last.next = null;
    delete map[last.key];
    this.length -= 1;
  }
  node = new TwoWayNode(key, value);
  map[key] = node;
  const first = head.next;
  node.next = first;
  first.pre = node;
  head.next = node;
  node.pre = head;
  this.length += 1;
};

const lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
console.log(lRUCache.get(1)); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
console.log(lRUCache.get(2)); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
console.log(lRUCache.get(1)); // 返回 -1 (未找到)
console.log(lRUCache.get(3)); // 返回 3
console.log(lRUCache.get(4)); // 返回 4
